package 二维前缀和_二维差分_离散化技巧;

// 边框为1的最大正方形
// 给你一个由若干 0 和 1 组成的二维网格 grid
// 请你找出边界全部由 1 组成的最大 正方形 子网格
// 并返回该子网格中的元素数量。如果不存在，则返回 0。
// 测试链接 : https://leetcode.cn/problems/largest-1-bordered-square/
public class Code02_LargestOneBorderedSquare {

    // 打败比例不高，但完全是常数时间的问题
    // 时间复杂度O(n * m * min(n,m))，额外空间复杂度O(1)
    // 复杂度指标上绝对是最优解
    public int largest1BorderedSquare(int[][] g) {
        // 行
        int n = g.length;
        // 列
        int m = g[0].length;
        build(g, n, m);
        // 原始的二维数组中就没有 1
        if (sum(g, 0, 0, n - 1, m - 1) == 0) {
            return 0;
        }
        // 找到的最大合法正方形的边长
        int ans = 1;
        for (int a = 0; a < n; a++) {
            for (int b = 0; b < m; b++) {
                // 上面两个for循环就是枚举 (a,b)所有左上角点
                //  下面是枚举 (c,d)更大边长的右下角点，k是当前尝试的边长
                // c = ans + a, d = ans + b ：本来应该是c = ans + 1, d = ans + 1，那为什么是 +ans呢？
                // 这里有一个剪枝：因为左上角来到（a, b）位置，ans的值经过更新，
                // 假如等于4, 那么则不必验证 a+1, b+1的正方形了
                for (int c = ans + a, d = ans + b, k = ans + 1; c < n && d < m; c++, d++, k++) {
                    // (k - 1) << 2 当前正方形的周长值
                    if (sum(g, a, b, c, d) - sum(g, a + 1, b + 1, c - 1, d - 1) == (k - 1) << 2) {
                        // 得到更大的答案
                        ans = k;
                    }
                }
            }
        }
        return ans * ans;
    }

    public static int sum(int[][] g, int a, int b, int c, int d) {
        // a > c ? 0  如果一个正方形的边长为2，则其没有内部，则内部的累加和为 0
        return a > c ? 0 : (g[c][d] - get(g, c, b - 1)
                - get(g, a - 1, d) + get(g, a - 1, b - 1));
    }

    // g : 原始二维数组
    // 把g变成原始二维数组的前缀和数组sum，复用自己
    // 不能补0
    public static void build(int[][] g, int n, int m) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 我自己的值 + 我的左 + 我的上 - 我的左上
                g[i][j] += get(g, i, j - 1) + get(g, i - 1, j)
                        - get(g, i - 1, j - 1);
            }
        }
    }

    // 在二维数组中得到 i,j 位置的值
    // （无论是构造前缀和数组的过程，还是通过前缀和数组求左上角(a,b)到右下角(c,d)这个范围的累加和的过程）
    public static int get(int[][] g, int i, int j) {
        // 如果越界了，则得到的值为：0
        return (i < 0 || j < 0) ? 0 : g[i][j];
    }
}
